public abstract class FiniteAutomata implements DrawableDiagram
{
	/*
	 * MEMBER VARIABLES
	 */
	
	// All states stored in _states.  _states[0] stores start state.  
	// Size of _states is increased as needed, in increments of 10.  
	protected State[] _states = new State[11];
	protected int _stateCount = 0;
	protected String[] _alphabet;
	protected ProxyDiagram _pd;
	
	
	
	/*
	 * CONSTRUCTORS
	 */
	
	// Create an empty FA
	public FiniteAutomata()
	{
		this._alphabet = new String[0];
	}
	
	// Create an FA from file
	public FiniteAutomata(String input)
	{
		parseSave(input);
	}
	
	
	
	/*
	 * ABSTRACT METHODS
	 */
	
	//abstract boolean simulate(String[] word);
	
	//abstract String isValid();
	
	
	
	/*
	 * CONCRETE METHODS
	 */	
	
	// Increases the size of this._states
	public void increaseStates()
	{
		State[] newStates = new State[this._states.length + 10];
		for (int i = 0; i < this._states.length; i++)
		{
			newStates[i] = this._states[i];
		}
		this._states = newStates;
	}
	
	// Adds a state to the FA.  Returns true if successful, false otherwise.
	public boolean addState(State state)
	{
		for (int i = 1; i <= this._stateCount; i++)
		{
			if (this._states[i].getName().equals(state.getName()))
			{
				return false; // Already have state by this name
			}
		}
		if (this._stateCount == this._states.length - 1)
		{
			this.increaseStates();
		}
		this._stateCount++;
		this._states[this._stateCount] = state;
		return true;
	}
	
	// Removes a state from the FA.  Returns true if successful, false
	// otherwise.  
	public boolean removeState(State state)
	{
		for (int i = 1; i <= this._stateCount; i++)
		{
			if (this._states[i].equals(state))
			{
				if (this._states[0].equals(state))
				{
					this._states[0] = null; // Removed start state
				}
				for (int j = i; j < this._stateCount; j++)
				{
					this._states[j] = this._states[j+1];
				}
				this._states[this._stateCount] = null; 
				this._stateCount--;
				return true;
			}
		}
		return false; // Never had this state to begin with
	}
	
	// Renames a state in the FA.  Returns true if successful, false otherwise.  
	public boolean renameState(State state, String newName)
	{
		for (int i = 1; i <= this._stateCount; i++)
		{
			if (this._states[i].equals(state))
			{
				boolean initial = false;
				if (this._states[0].equals(state)) { initial = true; }
				this._states[i].setName(newName);
				if (initial) { this._states[0] = this._states[i]; }
				return true;
			}
		}
		return false; // Don't contain the state you're trying to rename
	}
	
	// Adds a transition given only the names of the states involved.  
	public boolean addTransition(String initialState, String finalState, String letter)
	{
		State s1 = this.getStateFromName(initialState);
		State s2 = this.getStateFromName(finalState);
		boolean ans = this.addTransition(s1,  s2,  letter);
		return ans;
	}
	
	// Adds a transition.  Returns true if successful, false otherwise.  
	public boolean addTransition(State initialState, State finalState, String letter)
	{
		for (int i = 1; i <= this._stateCount; i++)
		{
			if (this._states[i].equals(initialState))
			{
				for (int j = 1; j <= this._stateCount; j++)
				{
					if (this._states[j].equals(finalState))
					{
						if (this.containsLetter(letter))
						{
							boolean initial = false;
							if (this._states[0].equals(initialState)) { initial = true; }
							this._states[i].addTransition(finalState, letter);
							if (initial) { this._states[0] = this._states[i]; }
							return true;
						}
						return false; // Don't contain letter
					}
				}
				return false; // Don't contain finalState
			}
		}
		return false; // Don't contain initialState
	}
	
	// Checks if this FA's alphabet contains letter.  
	public boolean containsLetter(String letter)
	{
		for (String l : this._alphabet)
		{
			if (l.equals(letter))
			{
				return true;
			}
		}
		return false;
	}
	
	// Removes a transition.  Returns true if successful, false otherwise.  
	public boolean removeTransition(State initialState, State finalState, String letter)
	{
		for (int i = 1; i <= this._stateCount; i++)
		{
			if (this._states[i].equals(initialState))
			{
				boolean initial = false;
				if (this._states[0].equals(initialState)) { initial = true; }
				if (this._states[i].removeTransition(finalState, letter))
				{
					if (initial) { this._states[0] = this._states[i]; }
					return true;
				}
				return false; // Transition did not exist
			}
		}
		return false; // initialState not part of this FA
	}
	
	// Sets the start state.  Returns true if successful, false otherwise.  
	public boolean setStartState(State state)
	{
		for (int i = 1; i <= this._stateCount; i++)
		{
			if (this._states[i].equals(state))
			{
				this._states[0] = state;
				return true;
			}
		}
		return false; // Don't contain state
	}
	
	// Returns a state in the FA by the name given, if any.  
	public State getStateFromName(String name)
	{
		for (int i = 1; i <= this._stateCount; i++)
		{
			if (this._states[i].getName().equals(name))
			{
				return this._states[i];
			}
		}
		return null; // Don't have a state by this name, bummer
	}
	
	public String getNewStateName()
	{
		return "state" + this._stateCount;
	}
	
	public int getIndexFromName(String name)
	{
		for (int i = 1; i <= this._stateCount; i++)
		{
			if (this._states[i].getName().equals(name))
			{
				return i;
			}
		}
		return -1;
	}
	
	// Draws the current FA.  
	public void draw()
	{
		for (int i = 1; i <= this._stateCount; i++)
		{
			this._pd.drawState(this._states[i]);
		}
		for (int i = 1; i <= this._stateCount; i++)
		{
			this._states[i].drawTransitions(this._pd, this);
		}
	}
	
	// Takes the current FA and creates save file text for it.  
	// Note that you can call this method even if the FA is not
	// valid or complete.  
	public String writeSave()
	{
		String alphabet = "";
		for (int i = 0; i < this._alphabet.length; i++)
		{
			alphabet += this._alphabet[i];
			if (i == this._alphabet.length - 1)
			{
				alphabet += ";";
			}
			else
			{
				alphabet += ",";
			}
		}
		String states = "";
		for (int i = 1; i <= this._stateCount; i++)
		{
			states += this._states[i].getName();
			int[] coords = this._states[i].getCoords();
			if (coords[0] != -1)
			{
				states += "[" + coords[0] + "]" + coords[1];
			}
			if (i == this._stateCount)
			{
				states += ";";
			}
			else
			{
				states += ",";
			}
		}
		String start = "";
		if (this._states[0] != null)
		{
			start = this._states[0].getName() + ";";
		}
		else
		{
			start = ";";
		}
		String accepting = "";
		boolean anyYet = false;
		for (int i = 1; i <= this._stateCount; i++)
		{
			if (this._states[i].getAccepting())
			{
				if (anyYet)
				{
					accepting += "," + this._states[i].getName();
				}
				else
				{
					accepting = this._states[i].getName();
					anyYet = true;
				}
			}
		}
		accepting += ";";
		String transition = "";
		anyYet = false;
		for (int i = 1; i <= this._stateCount; i++)
		{
			if (anyYet)
			{
				transition += ",";
			}
			String data = this._states[i].getTransitionData();
			if (data != "")
			{
				transition += data;
				anyYet = true;
			}
		}
		transition += ";";
		String pushdownData = "";
		if (this instanceof PushdownAutomata)
		{
			anyYet = false;
			for (int i = 1; i <= this._stateCount; i++)
			{
				if (anyYet)
				{
					transition += ",";
				}
				String data = ((PushdownState)this._states[i]).getOtherTransitionData();
				if (data != "")
				{
					pushdownData += data;
					anyYet = true;
				}
			}
			pushdownData += ";";
		}
		String fileText = alphabet + states + start + accepting + transition + pushdownData;
		return fileText;
	}
	
	/*
	 * File should contain no linebreaks or spaces (Unless the space 
	 * is a letter), and is broken up into five sections:  
	 * Section 1:  List all of the letters in the alphabet, separated 
	 * by commas.  Letters should only be allowed to be single characters.  
	 * Section 2:  List all of the states in the machine by name, 
	 * separated by commas.  If a state has position data associated 
	 * with it (So we can save custom positions in diagrams), indicate 
	 * the position by placing a [ after the state's name, then the x 
	 * coordinate of the state, then a ], then the y coordinate of the 
	 * state.  
	 * Section 3:  List the starting state by name.  
	 * Section 4:  List the accepting states by name, separated by commas.  
	 * Section 5:  List the transition data, separated by commas.  The 
	 * format for this is x+y=z, where x is a state, y is a letter, and 
	 * z is the state x transitions to when fed the letter y.  To indicate 
	 * an epsilon transition from x to z, simple put x+=z.  
	 * Section 6:  For Pushdown Automatas only.  This section includes the
	 * pop/push data for the transitions.  Each transition must have push/pop
	 * data, even if it's to push and pop the empty character.  To indicate
	 * that a transition from section five pops a and pushes b, add the string
	 * "a+b", without quotes, to this section.  Separate these by commas, and
	 * make sure they appear in the same order as the transitions in section
	 * five.  
	 * Section 7:  For Pushdown Automatas only.  List the stack alphabet 
	 * separated by commas.  
	 * Section 8:  For Pushdown Automatas only.  List the initial stack letter.  If 
	 * there is no initial letter, put a space, or else the file will parse incorrectly.  
	 * Sections are to be separated by a single semicolon.  
	 * 
	 * Reserved characters in alphabets should be:  
	 * Semicolon, ;.  Used in file format specification.  
	 * Comma, ,.  Used in file format specification.  
	 * Equals, =.  Used in file format specification.  
	 * Plus, +.  Used in file format specification.  
	 * Brackets, [ and ].  Used in file format specification.   
	 * Backslash, \.  Can cause errors, right?  Or does Java handle that?  
	 */
	public void parseSave(String filee)
	{
		String[] file = filee.split(";");
		if (file.length == 5 || file.length == 6)
		{
			// Add the alphabet
			this._alphabet = file[0].split(",");
			// Add the states and transitions
			String[] states = file[1].split(",");
			this._states = new State[states.length + 1];
			this._stateCount = 0;
			for (String state : states)
			{
				String[] stat = state.split("\\[");
				this._stateCount++;
				String name;
				String[] coords = {"-1", "-1"};
				if (stat.length == 1) // No coordinates specified
				{
					name = state;
				}
				else // Coordinates specified
				{
					name = stat[0];
					coords = stat[1].split("\\]");
				}
				if (file.length == 5)
				{
					this._states[this._stateCount]= new State(name, coords, file[4].split(",")); 
				}
				else if (file.length == 6)
				{
					this._states[this._stateCount] = new PushdownState(name, coords, file[4].split(","), file[5].split(","));
				}
			}
			// Set the start state
			for (int i = 1; i <= this._stateCount; i++)
			{
				if (this._states[i].getName().equals(file[2]))
				{
					this._states[0] = this._states[i];
					break;
				}
			}
			// Set accepting states
			states = file[3].split(",");
			for (String astate : states)
			{
				for (int i = 1; i <= this._stateCount; i++)
				{
					if (this._states[i].getName().equals(astate))
					{
						this._states[i].setAccepting(true);
						break;
					}
				}
			}
		}
		else
		{
			// File corrupted
			System.out.println("File error");
		}
	}
	
	public State[] getStates()
	{
		return this._states;
	}
	
	/*
	 * GETTERS AND SETTERS
	 */
	
	public void setAlphabet(String[] alphabet)
	{
		this._alphabet = alphabet;
	}
	
	public String[] getAlphabet()
	{
		return this._alphabet;
	}
	
	public void setProxyDiagram(ProxyDiagram proxy)
	{
		this._pd = proxy;
	}
	
	
	
	/*
	 * MAIN METHOD
	 */
	
	public static void main(String[] args)
	{
		// A PDA:  
		String input = "0,1;p,q,r,s;p;r;p+0=p,p+0=p,p+=q,p+1=s,q+1=q,q+0=s,q+=r,r+0=s,r+1=s,s+0=s,s+1=s;Z+AZ,A+AA,+,+,A+,+,Z+Z,+,+,+,+;A,Z;Z;";
		// http://i.imgur.com/dYGicQl.png
		// Another PDA:  
		// String input = "(,),x;a,b,c,d,e,f;a;e;a+=b,a+(=f,a+)=f,b+=c,b+(=b,b+x=b,b+)=b,b+)=f,c+=d,c+(=f,c+)=f,c+=e,d+=b,d+(=f,d+)=f,e+(=f,e+)=f,f+(=f,f+)=f;+$,+,+,t+,+(,+x,(+t,+,t+,+,+,$+,x+,+,+,+,+,+,+;(,),$,x,t; ;";
		// http://i.imgur.com/Qoj0NsE.png
		PushdownAutomata testPDA = new PushdownAutomata(input);
	}
}